package JianZhiOffer;

import JianZhiOffer.entity.TreeNNode;

import java.util.ArrayList;
import java.util.List;

public class TreeExample1 {
    public static void main(String[] args) {
        TreeNNode root = new TreeNNode(1);
        TreeNNode node2 = new TreeNNode(2);
        TreeNNode node3 = new TreeNNode(3);
        TreeNNode node4 = new TreeNNode(4);
        TreeNNode node5 = new TreeNNode(5);
        TreeNNode node6 = new TreeNNode(6);
        TreeNNode node7 = new TreeNNode(7);
        TreeNNode node8 = new TreeNNode(8);

        root.children.add(node2);
        root.children.add(node3);
        root.children.add(node4);
        node2.children.add(node5);
        node2.children.add(node6);
        node3.children.add(node7);
        node4.children.add(node8);

        int[] array = {2, 3};
        List<Integer> result = findNodesAndDescendants(root, array);
        System.out.println(result);
    }

    public static List<Integer> findNodesAndDescendants(TreeNNode root, int[] array) {
        List<Integer> result = new ArrayList<>();
        for (int value : array) {
            TreeNNode node = findNode(root, value);
            if (node != null) {
                collectValues(node, result);
            }
        }
        return result;
    }

    private static TreeNNode findNode(TreeNNode root, int value) {
        if (root == null) {
            return null;
        }
        if (root.val == value) {
            return root;
        }
        for (TreeNNode child : root.children) {
            TreeNNode found = findNode(child, value);
            if (found != null) {
                return found;
            }
        }
        return null;
    }

    private static void collectValues(TreeNNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        result.add(node.val);
        for (TreeNNode child : node.children) {
            collectValues(child, result);
        }
    }
}